COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	derive[f86,jmc]		Derived logic programs
C00004 ENDMK
C⊗;
derive[f86,jmc]		Derived logic programs

	The idea of derived programs arose in connection with LISP,
but it may have even more uses for logic programs.  The idea is
that intensional or, more specifically, operational properties
of a functional or logical program are not extensional properties of the
program regarded as a sentence of logic.  However, they
often turn out to be extensional properties of a related program.

	We begin with a LISP example.  The program

	$$flat[x,u] ← if \qat x \qthen x \. u \qelse flat[\qa x,flat[\qd x,u]]$$

flattens the list structure $x$ and appends it to the front of the
list $u$.  How many $cons$es are done in the computation is not
an extensional property of the program.  However, the {\it derived}
program

	$$cflat[x,u] ← if \qat x \qthen 1 \qelse cflat[\qa x,flat[\qd x,u]]
+ cflat[\qd x,u]$$

has as value the required number of $cons$es.